package 算法.leetcode.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author liclong
 * @create 2020-09-22 16:45
 * @desc 归并排序
 **/
public class MergeSort {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 7, 4, 9, 6};
        mergeSort(array, 0, array.length - 1);
        System.out.println(JSON.toJSONString(array));
    }

    public static void mergeSort(int[] array, int p, int r) {
        if (p >= r) {
            return;
        }

        int q = (p + r) / 2;
        mergeSort(array, p, q);
        mergeSort(array, q + 1, r);
        merge(array, p, q, r);
    }

    public static void merge(int[] array, int p, int q, int r) {

        // 初始化变量i, j, k
        int i = p, j = q + 1, k = 0;
        // 申请一个大小跟A[p...r]一样的临时数组
        int[] tmp = new int[r - p + 1];
        while (i <= q && j <= r) {
            if (array[i] <= array[j]) {
                tmp[k++] = array[i++];
            } else {
                tmp[k++] = array[j++];
            }
        }

        // 判断哪个子数组中有剩余的数据
        int start = i, end = q;
        if (j <= r) {
            start = j;
            end = r;
        }


        // 将剩余的数据拷贝到临时数组tmp
        while (start <= end) {
            tmp[k++] = array[start++];
        }

        // 将tmp中的数组拷贝回A[p...r]
        for (i = 0; i <= r - p; i++) {
            array[p + i] = tmp[i];
        }
        System.out.println(JSON.toJSONString(array));
    }
}
